package com.stephen.data.recursion;

/**
 * @author: stephen
 * @create: 2020-01-31 12:39
 * @description: 八皇后问题,回溯算法
 */
public class EightQueue {

    int max = 8;
    // 定义一个数组,保存最终的放置结果,如:int[] arr = {0,4,7,5,2,6,1,3};
    // 元素下标,表示行,从0开始
    // 元素的值,表示列,也从0开始,最大是7
    int[] arr = new int[max];

    static int count = 0;

    public static void main(String[] args) {
        EightQueue queue = new EightQueue();
        queue.check(0);
        System.out.printf("总共有%d种解法",count); // 92
    }

    /**
     * 放置第n个皇后,n 从0开始
     * @param n
     */
    private void check(int n) {
        if (n == max) { // n从0开始,=8时说明前7个已全部放好,打印结果即可
            print();
            return;
        }
        // 依次放入皇后,判断是否冲突
        for (int i = 0; i < max; i++) {
            // 先把当前皇后n,放到该行的第1列,其实是第0列
            arr[n] = i;
            if (judge(n)) { // 不冲突
                // 接着放n + 1个皇后
                check(n + 1);
            }
            // 如果冲突,就继续执行 arr[n] = i;
        }
    }

    /**
     *
     * @param n 表示第几个皇后
     * @return 是否冲突,true表示不冲突,false表示冲突
     */
    private boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            // arr[i]==arr[n]表示处于同一列
            // Math.abs(n-i)==Math.abs(arr[n]-arr[i])表示处于同一斜线
            if (arr[i] == arr[n] || Math.abs(n -i) == Math.abs(arr[n]-arr[i])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 输出皇后的位置
     */
    private void print() {
        count++;
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}
